1. Field of the Invention
The present invention relates to a method of moving in a minimum cost path using a grid map, and an apparatus to perform the method.
2. Description of the Related Art
Mobile home appliances must satisfy various conditions to move. They must be able to avoid obstacles, move in a manner to be suitable their functions, and reduce a movement distance.
Fixed obstacles, such as, for example, furniture and a bed, exist within indoor space where mobile home appliances typically move. When the positions of the furniture and the bed are input to a home appliance, the home appliance finds a shortest path avoiding the obstacles. However, new obstacles, such as a person, a chair, and/or other movable objects other than the obstacles that have been input to the home appliance, may be additionally brought to a movement space. For example, in a case in which only fixed furniture and a bed have been input as obstacles in a space, if someone brings a chair to the space, the chair becomes a new obstacle.
A conventional algorithm of planning a movement path using a grid map and executing movement has been proposed.
FIGS. 1A through 1C illustrate a conventional algorithm of planning an optimal path using a grid map. The algorithm is referred to as a D* algorithm [Anthony Stentz, “Optimal and Efficient Path Planning for Partially-Known Environment,” In Proceedings, IEEE International Conference on Robotics and Automation, 1994, 5]. According to the algorithm, a movement path is set based on a cell, and movement is performed in units of cells. When a new obstacle other than fixed obstacles is encountered, the movement path is partially replanned.
FIG. 1A illustrates initial grid map information set in a case in which the positions of obstacles are input before moving. A grid map has information regarding an optimal direction to move from each of a plurality of cells defined by dividing a movement area by a predetermined distance to a target point. FIG. 1A illustrates obstacle information of one room, and information regarding each cell. Fixed obstacles 10 exist in the room, and the target point is marked as “Goal.” The grid map of this example is divided into an area of 15×7 cells. One of eight directions is set to move from each cell to the Goal. The grid map shows that the target point is reached by moving straight from a start point marked as “Start”, even though the fixed obstacles 10 exist. A cell of the area marked “Start” indicates moving to the right, and a subsequent cell also indicates moving to the right. According to the indicated directions on the grid map, the target point can be reached by moving straight to the right. Moving according to the grid map shown in FIG. 1A is performed with no problems in the case in which only the fixed obstacles 10 exist.
However, when a new obstacle is added to the room, the movement path needs to be changed. When a new obstacle 20 is found as illustrated in FIG. 1B, the grid map in a region 50 should be changed. Since it is difficult to move to the right because of the new obstacle 20, the movement path is replanned to move around the fixed obstacles 10 and new obstacle 20. FIG. 1C shows a movement path on the changed grid map.
As shown in FIG. 1C, since the D* algorithm moves in cell units, movement may not be performed in the shortest path. When moving straight between a point illustrated in FIG. 1C and the “Goal”, a movement distance is 2.5 m. However, when movement between that same point and the “Goal” is performed in cell units, the movement distance is 3.5 m. To move in the shortest path, the size of a cell may be reduced. However, when the size of a cell is reduced, the size of data to be stored rapidly increases. For example, in a case in which a memory of 33 bytes is needed for a single cell, and a room having a size of 12×12 m is expressed in cells having a size of 20×20 cm, 3,600 cells must be calculated, and data of 3,600*33 bytes, i.e., 118,800 bytes, must be stored in memory. However, in a case in which the size of each cell is reduced to 10×10 cm, 14,400 cells must be calculated, and data of 14,000×33 bytes, i.e., 475,200 bytes, must be stored in memory. When the size of a cell is reduced by half, the size of data to be calculated is increased by a factor of four. Therefore, when the size of a cell is reduced to move in the shortest path, the size of the data to be stored is increased. Accordingly, it is preferable to not reduce the size of a cell.
Therefore, a method of moving in the shortest path while maintaining the size of a cell is desired. In addition, a method of moving in the shortest path by partially replanning a path when an unknown obstacle is encountered is desired, as well as an apparatus to perform the method.